1. Field of the Invention
The present invention relates to layout compaction for integrated circuit design automation, and more particularly to constraint graph-based layout compaction that compacts circuit elements in two dimensions during the design automation stage of a circuit layout with reduced computational requirements.
2. Description of Related Art
Compaction is an important design automation stage in the phased approach to layout synthesis of integrated circuits (ICs), such as a very large scale integration (VLSI) design. The compaction operation converts symbolic layouts generated by other layout synthesis tools into mask data or physical layouts and attempts to optimize the area of the layout without changing the circuit or violating the design rules. In other words, it is desired to make each chip as small as possible while maintaining design rule correctness (DRC). Today, the most attractive approach to mask layout compaction is graph-based compaction, which provides a robust basis for a one- and two-dimensional compaction.
Layout compaction algorithms typically range between one-dimensional and two-dimensional compaction. In one-dimensional compaction, only one coordinate of the layout geometry is changed at a time, such as either X compaction or Y compaction. The goal of one-dimensional compaction is to minimize the length of one dimension or direction, whereas the other direction, referred to as the shear or orthogonal direction, is not affected and remains constant. It is noted that dimension and direction are often used interchangeably herein. The goal of two-dimensional compaction is to modify both X and Y coordinates simultaneously in order to minimize area. Many one-dimensional compaction algorithm versions can be solved efficiently without consuming significant computational resources. A few proposed versions of one-dimensional compaction and most two-dimensional compaction proposals are xe2x80x9cNP-hardxe2x80x9d, which means that they are computationally prohibitive and not practicable. The difficulty of two-dimensional compaction lies in determining how the two dimensions of the layout interact to minimize the area. To circumvent the intrinsic complexity of this problem, some heuristic methods have been proposed to relate both dimensions of the compaction. Such heuristic proposals are often referred to as xe2x80x9c1.5-dimensionalxe2x80x9d compaction since, although they interrelate the two dimensions, they do not optimally solve the two-dimensional compaction problem.
Some 1.5-dimensional compaction methods have been proposed in which the layout is essentially compacted in a preferred direction, while changing the shear or orthogonal direction. In the process of achieving the primary goal of decreasing the extent of the layout in the preferred direction, these compaction techniques also make coordinate changes in the shear direction. Each local change is called a reorganization. One heuristic framework has been proposed, called xe2x80x9csuper compactionxe2x80x9d, for carrying out feasible reorganization such that the length of the longest path in the layout graph for the preferred direction is decreased. This approach is known as xe2x80x9cshearingxe2x80x9d compaction. Another method to minimize the critical path in the constraint graph is referred to as xe2x80x9cjog insertionxe2x80x9d.
Unfortunately, the shearing and jog insertion methods have been applied in sequence and have not been applied simultaneously. As a result, the existing algorithms cannot compact most layouts very efficiently. Shearing and jog insertion techniques in sequence can optimize the layout, but only if a sequence of the shearing and jog insertion methods are applied sequentially where each particular step improves the objective. The existing compaction algorithms, however, cannot apply critical path reduction techniques of shearing and jog insertion simultaneously and therefore optimal solutions are not available for most designs.